class Expression
{
public:
	virtual int interpreter(map<char,int> var) = 0;
	virtual ~Expression(){}
};

//变量表达式
class VarExpression:public Expression
{
	char key;
public:
	VarExpression(const char& key)
	{
		this->key = key;
	}
	int interpreter(map<char,int> var) override
	{
		return var[key];
	}
};

//符号表达式
class SymbolExpression:public Expression
{
	//运算符左右两个参数
protected:
	Expression* left;
	Expression* right;
public:
	SymbolExpression(Expression* left,Expression*right):left(left),right(right)
	{

	}
}

//加法
class AddExpression:public SymbolExpression
{
public:
	AddExpression(Expression* left,Expression*right):SymbolExpression(left,right)
	{

	}
	int interpreter(map<char,int> var) override
	{
		return left->interpreter(var) + right->interpreter(var);
	}
}

//减法
class SubExpression:public SymbolExpression
{
public:
	SubExpression(Expression* left,Expression*right):SymbolExpression(left,right)
	{

	}
	int interpreter(map<char,int> var) override 
	{
		return left->interpreter(var) - right->interpreter(var);
	}
}

Expression* analyse(string expStr)
{
	stack<Expression> expStack;
	Expression* left = nullptr;
	Expression* right = nullptr;
	for(int i = 0; i < expStr.size(); i++)
	{
		switch(expStr[i])
		{
			case '+':
				left = expStack.top();
				right = new VarExpression(expStr[++i]);
				expStack.push(new AddExpression(left,right));
				break;
			case '+':
				left = expStack.top();
				right = new VarExpression(expStr[++i]);
				expStack.push(new SubExpression(left,right));
				break;
			default:
				expStack.push(new VarExpression(expStr[i]));
		}
	}
	Expression* expression = expStack(expStr[i]);
	return expression;
}


void release(Expression* expression)
{
	//释放表达式树的内存
}

int main()
{
	string expStr = "a+b-c+d";
	map<char,int> var;
	var.insert(make_pair('a',5));
	var.insert(make_pair('b',2));
	var.insert(make_pair('c',1));
	var.insert(make_pair('d',6));

	Expression* expression = analyse(expStr);
	int result = expression->interpreter(var);
	//输出
	release(expression);
	return 0;
}